<!DOCTYPE html><html lang="zh"><head><meta charset="UTF-8"><script async src="https://www.googletagmanager.com/gtag/js?id=G-MP1THLPZFC"></script><script>function gtag(){dataLayer.push(arguments)}window.dataLayer=window.dataLayer||[],gtag("js",new Date),gtag("config","G-MP1THLPZFC")</script><script>var _hmt=_hmt||[];!function(){var e=document.createElement("script");e.src="https://hm.baidu.com/hm.js?956b14594152e1b71ce14695a71235d5";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1,minimum-scale=1"><meta http-equiv="X-UA-Compatible" content="ie=edge"><meta name="author" content="CS_GUIDER"><meta name="subtitle" content="If not now, when? If not me, who?"><meta name="description" content="欢迎来到我的CS_GUIDER博客！这里提供了全面、实用和最新的Java编程信息。你可以找到Java算法、项目、博客、数据库、Linux系统的教程和笔记。我致力于为您提供Java编程的实用指南和资源，包括Java框架、JVM和Git等。无论您是初学者还是经验丰富的开发人员，都可以从中获益。谢谢您的光临！"><meta name="keywords" content="Java,算法,项目,博客,数据库,Linux,框架,JVM,Git,编程,开发,教程"><title>我的算法随笔 | CS_GUIDER&#39;S Blog</title><link rel="icon" href="/favicon.ico"><link rel="stylesheet" href="/css/main.css"><link rel="stylesheet" href="/lib/nprogress/nprogress.css"><script src="/lib/jquery.min.js"></script><script src="/lib/iconify-icon.min.js"></script><script src="https://cdn.tailwindcss.com?plugins=typography"></script><script>tailwind.config={darkMode:"class"}</script><script src="/lib/nprogress/nprogress.js"></script><script>$(document).ready(()=>{NProgress.configure({showSpinner:!1}),NProgress.start(),$("#nprogress .bar").css({background:"#de7441"}),$("#nprogress .peg").css({"box-shadow":"0 0 2px #de7441, 0 0 4px #de7441"}),$("#nprogress .spinner-icon").css({"border-top-color":"#de7441","border-left-color":"#de7441"}),setTimeout((function(){NProgress.done(),$(".fade").removeClass("out")}),800)})</script><script>!function(){const e=window.matchMedia&&window.matchMedia("(prefers-color-scheme: dark)").matches,t=localStorage.getItem("hexo-color-scheme")||"auto";("dark"===t||e&&"light"!==t)&&document.documentElement.classList.toggle("dark",!0);document.documentElement.classList.contains("dark")}(),$(document).ready((function(){const e=window.matchMedia&&window.matchMedia("(prefers-color-scheme: dark)").matches,t=document.documentElement.classList.contains("dark");function o(){const e=document.documentElement.classList.contains("dark"),t=document.querySelector("iframe.giscus-frame");t&&t.contentWindow.postMessage({giscus:{setConfig:{theme:e?"dark":"light"}}},"https://giscus.app")}function n(){let t=document.documentElement.classList.contains("dark");localStorage.getItem("hexo-color-scheme");t=!t,document.documentElement.classList.toggle("dark",t),$("#theme-icon").attr("icon",t?"ri:moon-line":"ri:sun-line"),e===t?localStorage.setItem("hexo-color-scheme","auto"):localStorage.setItem("hexo-color-scheme",t?"dark":"light"),o()}$("#theme-icon").attr("icon",t?"ri:moon-line":"ri:sun-line"),window.matchMedia("(prefers-color-scheme: dark)").addEventListener("change",e=>{"auto"===(localStorage.getItem("hexo-color-scheme")||"auto")&&(document.documentElement.classList.toggle("dark",e.matches),$("#theme-icon").attr("icon",e.matches?"ri:moon-line":"ri:sun-line"),o())}),$("#toggle-dark").click(e=>{if(!(document.startViewTransition&&!window.matchMedia("(prefers-reduced-motion: reduce)").matches))return void n();const t=e.clientX,o=e.clientY,c=Math.hypot(Math.max(t,innerWidth-t),Math.max(o,innerHeight-o));document.startViewTransition(async()=>{n()}).ready.then(()=>{const e=document.documentElement.classList.contains("dark"),n=[`circle(0px at ${t}px ${o}px)`,`circle(${c}px at ${t}px ${o}px)`];document.documentElement.animate({clipPath:e?[...n].reverse():n},{duration:400,easing:"ease-out",pseudoElement:e?"::view-transition-old(root)":"::view-transition-new(root)"})})})}))</script><meta name="generator" content="Hexo 5.4.2"></head><body class="font-sans bg-white dark:bg-zinc-900 text-gray-700 dark:text-gray-200 relative"><header class="fixed w-full px-5 py-1 z-10 backdrop-blur-xl backdrop-saturate-150 border-b border-black/5"><div class="max-auto"><nav class="flex items-center text-base"><a href="/" class="group"><h2 class="font-medium tracking-tighterp text-l p-2"><img class="w-5 mr-2 inline-block transition-transform group-hover:rotate-[30deg]" id="logo" src="/img/logo.svg" alt="CS_GUIDER'S Blog"> CS_GUIDER&#39;S Blog</h2></a><div id="header-title" class="opacity-0 md:ml-2 md:mt-[0.1rem] text-xs font-medium whitespace-nowrap overflow-hidden overflow-ellipsis">我的算法随笔</div><div class="flex-1"></div><div class="flex items-center gap-3"><a class="hidden sm:flex" href="/">Home</a> <a class="hidden sm:flex" href="/archives">Archives</a> <a class="hidden sm:flex" href="/category">Categories</a> <a class="hidden sm:flex" href="/tag">Tags</a> <a class="w-5 h-5 hidden sm:flex" title="Github" target="_blank" rel="noopener" href="https://github.com/wl2o2o"><iconify-icon width="20" icon="ri:github-line"></iconify-icon></a><a class="w-5 h-5 hidden sm:flex" title="Github" href="rss2.xml"><iconify-icon width="20" icon="ri:rss-line"></iconify-icon></a><a class="w-5 h-5" title="toggle theme" id="toggle-dark"><iconify-icon width="20" icon="" id="theme-icon"></iconify-icon></a></div><div class="flex items-center justify-center gap-3 ml-3 sm:hidden"><span class="w-5 h-5" aria-hidden="true" role="img" id="open-menu"><iconify-icon width="20" icon="carbon:menu"></iconify-icon></span><span class="w-5 h-5 hidden" aria-hidden="true" role="img" id="close-menu"><iconify-icon width="20" icon="carbon:close"></iconify-icon></span></div></nav></div></header><div id="menu-panel" class="h-0 overflow-hidden sm:hidden fixed left-0 right-0 top-12 bottom-0 z-10"><div id="menu-content" class="relative z-20 bg-white/80 px-6 sm:px-8 py-2 backdrop-blur-xl -translate-y-full transition-transform duration-300"><ul class="nav flex flex-col sm:flex-row text-sm font-medium"><li class="nav-portfolio sm:mx-2 border-b sm:border-0 border-black/5 last:border-0 hover:text-main"><a href="/" class="flex h-12 sm:h-auto items-center">Home</a></li><li class="nav-portfolio sm:mx-2 border-b sm:border-0 border-black/5 last:border-0 hover:text-main"><a href="/archives" class="flex h-12 sm:h-auto items-center">Archives</a></li><li class="nav-portfolio sm:mx-2 border-b sm:border-0 border-black/5 last:border-0 hover:text-main"><a href="/category" class="flex h-12 sm:h-auto items-center">Categories</a></li><li class="nav-portfolio sm:mx-2 border-b sm:border-0 border-black/5 last:border-0 hover:text-main"><a href="/tag" class="flex h-12 sm:h-auto items-center">Tags</a></li></ul></div><div class="mask bg-black/20 absolute inset-0"></div></div><main class="pt-14"><link rel="stylesheet" href="/lib/fancybox/fancybox.min.css"><link rel="stylesheet" href="/lib/tocbot/tocbot.min.css"><nav class="post-toc toc text-sm w-48 relative top-32 right-0 opacity-70 hidden lg:block" style="position:fixed!important"></nav><section class="px-6 max-w-prose mx-auto md:px-0"><header class="overflow-hidden pt-6 pb-6 md:pt-12"><div class="pt-4 md:pt-6"><h1 id="article-title" class="text-[2rem] font-bold leading-snug mb-4 md:mb-6 md:text-[2.6rem]">我的算法随笔</h1><div><section class="flex items-center gap-3 text-sm"><span class="flex items-center gap-1"><iconify-icon width="18" icon="carbon-calendar"></iconify-icon><time>2025-09-17</time> </span><span class="text-gray-400">·</span> <span class="flex items-center gap-1"><iconify-icon width="18" icon="ic:round-access-alarm"></iconify-icon><span>53 min</span> </span><span class="text-gray-400">·</span> <span class="flex items-center gap-1"><iconify-icon width="18" icon="icon-park-outline:font-search"></iconify-icon><span>11.9k words</span> </span><span class="text-gray-400">·</span> <span class="flex items-center gap-1"><iconify-icon width="16" icon="icon-park-outline:box" class="mr-2"></iconify-icon><a class="article-category-link" href="/categories/Java-U8G/">Java U8G</a></span></section></div></div></header><article class="post-content prose m-auto slide-enter-content dark:prose-invert"><h1 id="第一章-基础数学思维与技巧"><a href="#第一章-基础数学思维与技巧" class="headerlink" title="第一章 基础数学思维与技巧"></a>第一章 基础数学思维与技巧</h1><h2 id="最大公约数"><a href="#最大公约数" class="headerlink" title="最大公约数"></a>最大公约数</h2><h4 id="求最大公约数—-欧几里得辗转相除法"><a href="#求最大公约数—-欧几里得辗转相除法" class="headerlink" title="求最大公约数—-欧几里得辗转相除法"></a>求最大公约数—-欧几里得辗转相除法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">gcd</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span>&#123;</span><br><span class="line">   	<span class="keyword">while</span>(b&gt;<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> a%b;</span><br><span class="line">        a=b;</span><br><span class="line">        b=temp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">gcd</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> b==<span class="number">0</span>?a:gcd(b,a%b);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="最小公倍数"><a href="#最小公倍数" class="headerlink" title="最小公倍数"></a>最小公倍数</h2><h4 id="求最大公倍数"><a href="#求最大公倍数" class="headerlink" title="求最大公倍数"></a>求最大公倍数</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">lcm</span><span class="params">(<span class="type">int</span> a,<span class="type">int</span> b)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a * b / gcd(a,b);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="进制转换"><a href="#进制转换" class="headerlink" title="进制转换"></a>进制转换</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">String</span> <span class="variable">s</span> <span class="operator">=</span> Integer.toString(a,m);<span class="comment">//10进制a数转m进制数,结果为字符串</span></span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="variable">a</span> <span class="operator">=</span> Integer.parseInt(s,m);<span class="comment">//把字符串s当做m进制数,将结果转为10进制数</span></span><br><span class="line"></span><br><span class="line"><span class="type">BigInteger</span> <span class="variable">biginteger</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BigInteger</span>(s,m);<span class="comment">//把m进制的字符串s转换成10进制数后封装成大数对象</span></span><br></pre></td></tr></table></figure><h2 id="位运算"><a href="#位运算" class="headerlink" title="位运算"></a>位运算</h2><h3 id="与-amp-全1为1-有0为0"><a href="#与-amp-全1为1-有0为0" class="headerlink" title="与 &amp; (全1为1,有0为0)"></a>与 &amp; (全1为1,有0为0)</h3><h4 id="判断奇偶数"><a href="#判断奇偶数" class="headerlink" title="判断奇偶数"></a>判断奇偶数</h4><p>奇数-二进制最后一位一定为1<br>偶数-二进制最后一位一定为0</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span> m)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (m&amp;<span class="number">1</span>)==<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="判断m是否为2的x次方"><a href="#判断m是否为2的x次方" class="headerlink" title="判断m是否为2的x次方"></a>判断m是否为2的x次方</h4><p>若m为2的x次方:m的二进制只有最高位为1,其余全为0,(m-1)的二进制除最高位都为1.</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span> m)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> m&amp;(m-<span class="number">1</span>)==<span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="异或-相同为0-不同为1"><a href="#异或-相同为0-不同为1" class="headerlink" title="异或 ^ (相同为0,不同为1)"></a>异或 ^ (相同为0,不同为1)</h3><h4 id="找到数组中只出现了一次的数"><a href="#找到数组中只出现了一次的数" class="headerlink" title="找到数组中只出现了一次的数"></a>找到数组中只出现了一次的数</h4><p>按位异或：相同为0，不同为1</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">x^x=<span class="number">0</span>;</span><br><span class="line"><span class="number">0</span>^x=x;</span><br><span class="line">a^b^c=a^c^b;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">num</span><span class="params">(<span class="type">int</span>[] s)</span>&#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;s.length;i++)&#123;</span><br><span class="line">        ans = ans ^ s[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="移位-gt-gt-和-lt-lt"><a href="#移位-gt-gt-和-lt-lt" class="headerlink" title="移位 &gt;&gt; 和&lt;&lt;"></a>移位 &gt;&gt; 和&lt;&lt;</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">8</span>&gt;&gt;<span class="number">1</span> == <span class="number">4</span></span><br><span class="line"><span class="number">4</span>&gt;&gt;<span class="number">1</span> == <span class="number">2</span></span><br><span class="line">    </span><br><span class="line"><span class="number">2</span>&lt;&lt;<span class="number">1</span> == <span class="number">4</span></span><br><span class="line"><span class="number">4</span>&lt;&lt;<span class="number">1</span> == <span class="number">8</span></span><br><span class="line"></span><br><span class="line">n &gt;&gt; m == n / (<span class="number">2</span> ^ m)</span><br><span class="line">n &lt;&lt; m == n * (<span class="number">2</span> ^ m)</span><br></pre></td></tr></table></figure><h2 id="素数"><a href="#素数" class="headerlink" title="素数"></a>素数</h2><h4 id="判断素数"><a href="#判断素数" class="headerlink" title="判断素数"></a>判断素数</h4><p>素数:只有1和它本身是因数 。</p><p>首先，0和1不是素数，然后 i 从 2 开始判断 i 是不是 n 的因数，如果是因数，则直接返回 n 不是素数，否则，判断 i+1是不是 n 的因数，直到 i=√n 的时候，如果 i 仍然不是 n 的因数，那么 n 就是素数。</p><p>注：如果一个数 a 能够整除 i ，那么 i 和 a/i 一定满足：假设 i&lt;=a/i , 那么 i&lt;=√n , &amp;&amp; a/i&gt;= √n 。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">isprime</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span> || n==<span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n/i;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(n%i==<span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="求1-n中的所有素数—-埃氏筛法"><a href="#求1-n中的所有素数—-埃氏筛法" class="headerlink" title="求1~n中的所有素数—-埃氏筛法"></a>求1~n中的所有素数—-埃氏筛法</h4><p>思路：如果一个数不是素数，那么这个数一定是 n 个素数的乘积（0和1除外），同理，素数的 k 倍数一定是合数（k&gt;=2）。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">isprime</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    <span class="type">boolean</span>[] isprime = <span class="keyword">new</span> <span class="title class_">boolean</span>[n+<span class="number">1</span>];<span class="comment">//false表示素数，true表示合数</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i*i&lt;=n;i++) </span><br><span class="line">        <span class="keyword">if</span>(!isprime[i]) <span class="comment">//i是质数</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">2</span>;j*i&lt;=n;j++)<span class="comment">//将i的倍数全部标记为合数</span></span><br><span class="line">                isprime[i*j] = <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="keyword">if</span>(!isprime[i])</span><br><span class="line">            System.out.println(i);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="求1-n中的所有素数—-欧拉筛法"><a href="#求1-n中的所有素数—-欧拉筛法" class="headerlink" title="求1~n中的所有素数—-欧拉筛法"></a>求1~n中的所有素数—-欧拉筛法</h4><p>思路：每个合数，只被他最小的质因子筛一次。</p><p>注：与埃氏筛法不同，埃氏筛法是将素数的倍数，标记为合数；欧拉筛法是将目前已经找到的每一个素数的 i 倍标记为合数，无论 i 是否是素数，同时，如果 i 本身就是素数的倍数，那么就去执行下一个 i 。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">isprime</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    <span class="type">boolean</span>[] isprime = <span class="keyword">new</span> <span class="title class_">boolean</span>[n+<span class="number">1</span>];</span><br><span class="line">    <span class="type">int</span>[] prime = <span class="keyword">new</span> <span class="title class_">int</span>[n];<span class="comment">//存储素数</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">count</span> <span class="operator">=</span> <span class="number">0</span>;<span class="comment">//统计目前素数个数</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(!isprime[i])  <span class="comment">//i是质数</span></span><br><span class="line">            prime[count++] = i;<span class="comment">//把当前素数存储到数组中count位置</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;count &amp;&amp; i*prime[j]&lt;=n;j++)&#123;<span class="comment">//将i的倍数全部标记为合数</span></span><br><span class="line">            isprime[i*prime[j]] = <span class="literal">true</span>;</span><br><span class="line">            <span class="keyword">if</span>(i%prime[j]==<span class="number">0</span>) <span class="keyword">break</span>;<span class="comment">//欧拉筛法精髓</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;count;i++)</span><br><span class="line">        System.out.println(prime[i]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="例题：最小质因子之和"><a href="#例题：最小质因子之和" class="headerlink" title="例题：最小质因子之和"></a>例题：最小质因子之和</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1151/learning/">最小质因子之和(Easy Version) - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102197.png" alt="最小质因子之和题目描述"></p><p>思路：因为题目输入为T组数据，如果单独计算每组数据，则会有部分区间的数据被重复计算，所以先通过埃氏筛法，求出每一个数的最小质因子，将结果存放在 ans 数组中，然后将 ans 数组表示为前缀和数组，此时 ans 数组中的结果就为2~n的质因子之和，此时，题目若输入 15 ，则直接输出 ans[15] 即可。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 最小质因子之和 &#123;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">boolean</span>[] isprime  = <span class="keyword">new</span> <span class="title class_">boolean</span>[<span class="number">3000001</span>];<span class="comment">//是否是素数</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">long</span>[] ans = <span class="keyword">new</span> <span class="title class_">long</span>[<span class="number">3000001</span>];<span class="comment">//存储最小质因子 i的最小质因子为ans[i]，例：ans[4] = 2</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">	<span class="keyword">static</span> <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException&#123;</span><br><span class="line">		get(<span class="number">3000000</span>);<span class="comment">//题目数据范围，N最大值为3*10^6，将2~3*10^6中每一个数的最小质因子全部求出</span></span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=<span class="number">3000000</span>;i++) &#123;</span><br><span class="line">			ans[i] = ans[i] + ans[i-<span class="number">1</span>];<span class="comment">//求前缀和，此时ans[i]中存放的数就是2~i中每一个数的最小质因子的和</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> Integer.parseInt(in.readLine());</span><br><span class="line">		<span class="keyword">while</span>(n--&gt;<span class="number">0</span>) &#123;</span><br><span class="line">			out.println(ans[Integer.parseInt(in.readLine())]);</span><br><span class="line">		&#125;</span><br><span class="line">		out.flush();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//找出每个数的质因子</span></span><br><span class="line">	<span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">get</span><span class="params">(<span class="type">int</span> n)</span> &#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(isprime[i])<span class="comment">//i不是质数直接跳过,不考虑,i不能作为筛除条件</span></span><br><span class="line">				<span class="keyword">continue</span>;</span><br><span class="line">			ans[i] = i;<span class="comment">//i为素数，素数的最小质因子就是其本身</span></span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">2</span>;j&lt;=n/i;j++) &#123;<span class="comment">//j为倍数，将素数i的j倍数标记为合数，并将此数的最小质因子标记为i</span></span><br><span class="line">				<span class="keyword">if</span>(!isprime[j*i]) &#123;<span class="comment">//判断是否已经被标记过</span></span><br><span class="line">					isprime[j*i] = <span class="literal">true</span>;<span class="comment">//将i*j标记为合数</span></span><br><span class="line">					ans[j*i] = i;<span class="comment">//j*i的最小质因子是i</span></span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="回文数"><a href="#回文数" class="headerlink" title="回文数"></a>回文数</h2><h4 id="判断回文数"><a href="#判断回文数" class="headerlink" title="判断回文数"></a>判断回文数</h4><p>思路：将数字转换为字符串类型后，将此字符串倒转后，判断与原字符串是否相同</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span> m)</span>&#123;</span><br><span class="line">    <span class="keyword">return</span> Integer.toString(m).equals(<span class="keyword">new</span> <span class="title class_">StringBuffer</span>(Integer.toString(m)).reverse().toString());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="判断数组中元素是否相同"><a href="#判断数组中元素是否相同" class="headerlink" title="判断数组中元素是否相同"></a>判断数组中元素是否相同</h2><p>思路：若数组中元素全部相同，则数组中的最大值应当==最小值。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span>[] n)</span>&#123;</span><br><span class="line">    Arrays.sort(n);</span><br><span class="line">    <span class="keyword">return</span> n[<span class="number">0</span>]==n[n.length-<span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>思路：利用Set集合自动去重，将数组中所有元素全部添加到集合中后，如果集合中只有一个元素，则表示数组中所有元素全部相同。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span>[] n)</span>&#123;</span><br><span class="line">    Set&lt;Integer&gt; set = <span class="keyword">new</span> <span class="title class_">HashSet</span>&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n.length;i++) &#123;</span><br><span class="line">        set.add(n[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> set.size()==<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="日期-星期模拟"><a href="#日期-星期模拟" class="headerlink" title="日期+星期模拟"></a>日期+星期模拟</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> Main&#123;</span><br><span class="line">    <span class="keyword">static</span> <span class="type">int</span>[] date = &#123;<span class="number">0</span>,<span class="number">31</span>,<span class="number">28</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>,<span class="number">30</span>,<span class="number">31</span>&#125;;<span class="comment">//存储每月天数</span></span><br><span class="line">    <span class="keyword">static</span> <span class="type">int</span> <span class="variable">y</span> <span class="operator">=</span> <span class="number">2001</span>,m = <span class="number">1</span>;d = <span class="number">1</span>,week = <span class="number">1</span>;<span class="comment">//初始年,月,日,星期(根据题意选择是否需要)</span></span><br><span class="line">    <span class="comment">//week==0,表示周日,week==1,表示周一 ... week==6,表示周六</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;<span class="comment">//计数</span></span><br><span class="line">        <span class="keyword">while</span>(y!=<span class="number">9999</span> || m!=<span class="number">12</span>|| d!=<span class="number">31</span>)&#123;<span class="comment">//设置日期判断范围</span></span><br><span class="line">            <span class="comment">//判断闰年(满足其一即可):</span></span><br><span class="line">            <span class="comment">//1.可以整除400</span></span><br><span class="line">            <span class="comment">//2.可以整除4但不能整除100</span></span><br><span class="line">            <span class="keyword">if</span>(y%<span class="number">400</span>==<span class="number">0</span> || (y%<span class="number">4</span>==<span class="number">0</span>&amp;&amp; y%<span class="number">100</span>!=<span class="number">0</span>) date[<span class="number">2</span>] = <span class="number">29</span>;</span><br><span class="line">            <span class="keyword">else</span> date[<span class="number">2</span>] = <span class="number">28</span>;</span><br><span class="line">            <span class="keyword">if</span>(check()) ans++;<span class="comment">//满足条件,计数器++;</span></span><br><span class="line">            d++;</span><br><span class="line">            week++;</span><br><span class="line">            week%=<span class="number">7</span>;</span><br><span class="line">            <span class="keyword">if</span>(d&gt;date[m])&#123;</span><br><span class="line">                d = <span class="number">1</span>;</span><br><span class="line">                m++;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(m&gt;<span class="number">12</span>)&#123;</span><br><span class="line">                m = <span class="number">1</span>;</span><br><span class="line">                y++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(check()) ans++;<span class="comment">//之前结束日期并未判断,判断结束日期</span></span><br><span class="line">        System.out.println(ans);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">()</span>&#123;&#125;<span class="comment">//根据题目要求完成</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="约数"><a href="#约数" class="headerlink" title="约数"></a>约数</h2><h4 id="唯一分解定理"><a href="#唯一分解定理" class="headerlink" title="唯一分解定理"></a>唯一分解定理</h4><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102199.png" alt="image-20231118203136873"></p><h4 id="n的质因数个数—-唯一分解定理"><a href="#n的质因数个数—-唯一分解定理" class="headerlink" title="n的质因数个数—-唯一分解定理"></a>n的质因数个数—-唯一分解定理</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">num</span><span class="params">(<span class="type">long</span> n)</span>&#123;   </span><br><span class="line">    <span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;    </span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n/i;i++)&#123;        </span><br><span class="line">        <span class="keyword">while</span>(n%i==<span class="number">0</span>)&#123;            </span><br><span class="line">            ans++;              </span><br><span class="line">            n/=i;        </span><br><span class="line">        &#125;    </span><br><span class="line">    &#125;    </span><br><span class="line">    <span class="keyword">if</span>(n&gt;<span class="number">1</span>)        </span><br><span class="line">        ans++;    </span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="n的约数个数—-唯一分解定理"><a href="#n的约数个数—-唯一分解定理" class="headerlink" title="n的约数个数—-唯一分解定理"></a>n的约数个数—-唯一分解定理</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">num</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">cnt</span> <span class="operator">=</span> <span class="number">1</span>;<span class="comment">//乘法初始值为1</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">bak</span> <span class="operator">=</span> n;<span class="comment">//备份n</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i*i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">sum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(bak%i==<span class="number">0</span>)&#123;</span><br><span class="line">            sum++;</span><br><span class="line">            bak = bak / i;</span><br><span class="line">        &#125;</span><br><span class="line">        cnt = cnt * (sum + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(bak&gt;<span class="number">1</span>) cnt*=<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">return</span> cnt;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="求n-的约数个数—-唯一分解定理"><a href="#求n-的约数个数—-唯一分解定理" class="headerlink" title="求n!的约数个数—-唯一分解定理"></a>求n!的约数个数—-唯一分解定理</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">long</span> <span class="title function_">num</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    <span class="type">int</span>[] prime = <span class="keyword">new</span> <span class="title class_">int</span>[n+<span class="number">1</span>];<span class="comment">//prime[i]表示素数i这个因子出现的次数</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">bak</span> <span class="operator">=</span> i;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">2</span>;j*j&lt;=bak;j++)&#123;</span><br><span class="line">            <span class="type">int</span> <span class="variable">sum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">while</span>(bak%j==<span class="number">0</span>)&#123;</span><br><span class="line">                prime[j]++;</span><br><span class="line">                bak = bak / j;</span><br><span class="line">            &#125;</span><br><span class="line">    	&#125;</span><br><span class="line">    	<span class="keyword">if</span>(bak&gt;<span class="number">1</span>) prime[bak]++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">long</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(prime[i]&gt;<span class="number">1</span>)</span><br><span class="line">            ans = ans * (prime[i]+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans;	</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="例题：数数"><a href="#例题：数数" class="headerlink" title="例题：数数"></a>例题：数数</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/2218/learning/">数数 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102200.png" alt="image-20231118203219627"></p><p>思路：将这个区间中的每一个数都根据唯一分解定理进行拆分，统计有多少个数的拆分结果为12</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Scanner;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 数数 &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="type">Scanner</span> <span class="variable">sc</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">		<span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2333333</span>;i&lt;=<span class="number">23333333</span>;i++)</span><br><span class="line">			<span class="keyword">if</span>(num(i)==<span class="number">12</span>)</span><br><span class="line">				ans++;</span><br><span class="line">		System.out.println(ans);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> <span class="title function_">num</span><span class="params">(<span class="type">int</span> n)</span> &#123;</span><br><span class="line">		<span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">2</span>;i&lt;=n/i;i++) &#123;</span><br><span class="line">			<span class="keyword">while</span>(n%i==<span class="number">0</span>) &#123;</span><br><span class="line">				n/=i;</span><br><span class="line">				ans++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(n&gt;<span class="number">1</span>)</span><br><span class="line">			ans++;</span><br><span class="line">		<span class="keyword">return</span> ans;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h4 id="例题：求阶乘"><a href="#例题：求阶乘" class="headerlink" title="例题：求阶乘"></a>例题：求阶乘</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/2145/learning/">求阶乘 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102201.png" alt="image-20231118203313070"></p><p>思路：</p><p>​ 1.根据唯一分解定理可知：每一个数都可以写为 n 个素数的乘积；</p><p>​ 2.如果一个数的结尾有 0 的存在，那么这个数分解后一定有 2 和 5 （素数中，只有2 * 5才能使结尾产生 0 ）；</p><p>​ 3.从 1 ~ N ，将每一个数都分解后，2 的数量一定比 5 多（ 2 每隔两个数就会最少出现一个，5 每隔5个数，最少出现一个），那么，N！末尾 0 的数量，就是将 1 ~ N 中每个数分解后，5 的数量；</p><p>​ 4.如果用一个循环从 5 开始，每次 +5 ，判断这些数可以拆分出几个 5 ，然后去找结尾有 k 个 0 的最小的 N 是多少，这个方法结果正确，但是时间复杂度会比较高，所以借助二分，去找到结尾有 k 个 0 的最小的 N 是多少；</p><p>​ 5.用二分去查找，就必须做到：已知 N ，求出 1 ~ N 中可以拆分出多少个 5 ，以 125 为例，因为每五个数才拆分出 5 ，所以，如果 1~125 都只拆一个 5 ，则可以拆分出 125 / 5 共 25 个 5 ，拆分后的结果为 1 ~ 25 ，然后继续拆分 5 ，1 ~ 25 可以拆分出 25 / 5 个 5 ，拆分后结果为 1 ~ 5 ，1 ~ 5 可以拆分出 5 / 5 个 5 ，最后剩余 1 ，1 无法继续拆分出 5 ，所以 125 可以拆分出 25 + 5 + 1 = 31 个 5 ；</p><p>​ 6.二分：如果mid拆分出的 5 的数量 &gt;= k，那么可以 right = mid ，反之left = mid + 1，二分结果后，还需要判断它是否确实能拆分出 k 个 5 ，因为存在一个 N! 能恰好末尾有 k 个 0 ；</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Scanner;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 求阶乘 &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">long</span> <span class="title function_">find</span><span class="params">(<span class="type">long</span> x)</span> &#123;<span class="comment">//求x能拆分出多少个5</span></span><br><span class="line">		<span class="type">long</span> <span class="variable">res</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">while</span>(x != <span class="number">0</span>) &#123;</span><br><span class="line">			res = res + x / <span class="number">5</span>;</span><br><span class="line">			x/=<span class="number">5</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> res;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="type">Scanner</span> <span class="variable">sc</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">		<span class="type">long</span> <span class="variable">k</span> <span class="operator">=</span> sc.nextLong();</span><br><span class="line">		<span class="type">long</span> <span class="variable">l</span> <span class="operator">=</span> <span class="number">0</span>,r = <span class="number">100000</span>;<span class="comment">//防止溢出</span></span><br><span class="line">		<span class="keyword">while</span>(l &lt; r) &#123;</span><br><span class="line">			<span class="type">long</span> <span class="variable">mid</span> <span class="operator">=</span> (l + r) / <span class="number">2</span>;</span><br><span class="line">			<span class="keyword">if</span>(k &lt;= find(mid)) &#123;</span><br><span class="line">				r = mid;</span><br><span class="line">			&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">				l = mid + <span class="number">1</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(find(r) != k) &#123;<span class="comment">//确保有解</span></span><br><span class="line">			System.out.println(-<span class="number">1</span>);</span><br><span class="line">		&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">			System.out.println(r);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第二章-字符串基础"><a href="#第二章-字符串基础" class="headerlink" title="第二章 字符串基础"></a>第二章 字符串基础</h1><h2 id="常用API"><a href="#常用API" class="headerlink" title="常用API"></a>常用API</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">String</span> <span class="variable">m</span> <span class="operator">=</span> <span class="string">&quot;abcde&quot;</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> <span class="variable">ch</span> <span class="operator">=</span> m.charAt(String n);<span class="comment">//获取字符串m的第(n+1)个字符</span></span><br><span class="line"><span class="type">int</span> <span class="variable">length</span> <span class="operator">=</span> m.length();<span class="comment">//获取字符串m的长度</span></span><br><span class="line"><span class="type">boolean</span> <span class="variable">flag</span> <span class="operator">=</span> m.equals(String n);<span class="comment">//判断字符串m和n是否相等,严格区分大小写</span></span><br><span class="line"><span class="type">boolean</span> <span class="variable">flag</span> <span class="operator">=</span> m.equalsIgnoreCase(String n);<span class="comment">//判断字符串m和n是否相等,不区分大小写</span></span><br><span class="line"><span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> m.index(String s);<span class="comment">//返回字符串s在m中第一次出现的位置</span></span><br><span class="line"><span class="type">int</span> <span class="variable">compare</span> <span class="operator">=</span> m.compareTo(String anotherString);<span class="comment">//按字典序比较两个字符串,若compare&gt;0,m大,若compare&lt;0,m小</span></span><br><span class="line"><span class="type">String</span> <span class="variable">s</span> <span class="operator">=</span> m.concat(n);<span class="comment">//将字符串n拼接到字符串m的结尾</span></span><br><span class="line"><span class="type">boolean</span> <span class="variable">flag</span> <span class="operator">=</span> m.contains(String n);<span class="comment">//判断字符串m是否包含字符串n</span></span><br><span class="line"><span class="type">boolean</span> <span class="variable">flag</span> <span class="operator">=</span> m.endsWith(String s);<span class="comment">//判断字符串m是否以字符串s结尾</span></span><br><span class="line">String[] s = m.split(<span class="string">&quot; &quot;</span>);<span class="comment">//根据正则表达式拆分字符串m</span></span><br><span class="line"><span class="type">String</span> <span class="variable">s</span> <span class="operator">=</span> m.trim();<span class="comment">//删除字符串m的前导空格和尾部空格</span></span><br><span class="line"><span class="type">String</span> <span class="variable">s</span> <span class="operator">=</span> m.subString(<span class="type">int</span> i,<span class="type">int</span> j);<span class="comment">//截取字符串m中下标为i至下标为j-1的部分,即[i,j);</span></span><br><span class="line">...</span><br></pre></td></tr></table></figure><h2 id="周期串"><a href="#周期串" class="headerlink" title="周期串"></a>周期串</h2><p>思路：从 1 开始枚举周期 T 的大小，然后判断每个周期内的对应字符是否相同，如果不同，则直接判断下一个 T 。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">cycle</span><span class="params">(String s)</span>&#123;</span><br><span class="line">    <span class="type">char</span>[] ch = s.toCharArray();</span><br><span class="line">    <span class="type">int</span> T;</span><br><span class="line">    <span class="keyword">for</span>(T=<span class="number">1</span>;T&lt;=ch.length;T++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(ch.length%T==<span class="number">0</span>)&#123;<span class="comment">//周期串的长度一定是周期T的倍数</span></span><br><span class="line">            <span class="type">boolean</span> <span class="variable">flag</span> <span class="operator">=</span> <span class="literal">true</span>;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">start</span> <span class="operator">=</span> T;start&lt;ch.length;start++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(ch[start]!=ch[start%T])&#123;</span><br><span class="line">                    flag = <span class="literal">false</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(flag)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> T;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>思路：pos 表示第二行的字符串向右移动的格数，如果移动后，第二行的字符串与第一行字符串对应位置的字符全部相同，则 pos 就是这个字符串的周期。</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102202.png" alt="image-20231118203417476"></p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">cycle</span><span class="params">(String s)</span>&#123;</span><br><span class="line">	<span class="type">String</span> <span class="variable">m</span> <span class="operator">=</span> s+s;</span><br><span class="line">    <span class="type">int</span> pos;</span><br><span class="line">    <span class="keyword">for</span>(pos=<span class="number">1</span>;pos&lt;=s.length();pos++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.length()%pos!=<span class="number">0</span>)</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        <span class="type">String</span> <span class="variable">x</span> <span class="operator">=</span> m.substring(pos,pos+s.length());</span><br><span class="line">        <span class="keyword">if</span>(x.equals(s))</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pos;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>思路：如果一个字符串 sub 是字符串 s 的周期，那么将字符串 s 中所有的 sub 全部替换为空字符串之后，字符串的长度如果为 0 ，就表示字符串 sub 是字符串 s 的周期。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">cycle</span><span class="params">(String s)</span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=s.length();i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.length()%i==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">sub</span> <span class="operator">=</span> s.substring(<span class="number">0</span>,i);</span><br><span class="line">            <span class="keyword">if</span>(s.replace(sub,<span class="string">&quot;&quot;</span>).length()==<span class="number">0</span>)</span><br><span class="line">                <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="例题：重复字符串"><a href="#例题：重复字符串" class="headerlink" title="例题：重复字符串"></a>例题：重复字符串</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1049/learning/">重复字符串 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102203.png" alt="image-20231118203511964"></p><p>思路：已知重复次数为 K ，那么周期就是 S.length() / K ，然后只需要求出每一个周期的第 i 个字符，出现次数最多的字符是哪个，然后将其余字符全部改为它，那么就将 S 改为了重复 K 次的字符串，此时修改次数也是最少的。以abdcbbcaabca ， 重复 3 次为例：</p><p>​ 将此字符串拆分为三个部分后，每个周期写在一行，结果为：</p><p>​ abdc<br>​ bbca<br>​ abca</p><p>​ 只需要求出每一个竖列出现次数最多的字符出现的次数，然后将其余字符全部改为它，那么这一列修改次数为（K - max），然后将每一列的结果加起来，即为答案。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 重复字符串 &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">static</span> <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">	<span class="keyword">static</span> <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException &#123;</span><br><span class="line">		<span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> Integer.parseInt(in.readLine());</span><br><span class="line">		<span class="type">String</span> <span class="variable">a</span> <span class="operator">=</span> in.readLine();</span><br><span class="line">		<span class="keyword">if</span>(a.length()%n!=<span class="number">0</span> || n&gt;a.length()) &#123;</span><br><span class="line">			System.out.println(-<span class="number">1</span>);</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="type">int</span> <span class="variable">t</span> <span class="operator">=</span> a.length() / n;</span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">char</span>[][] ch = <span class="keyword">new</span> <span class="title class_">char</span>[n][t];</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;n;i++) </span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;t;j++)</span><br><span class="line">				ch[i][j] = a.charAt(index++);</span><br><span class="line">		<span class="type">int</span> <span class="variable">ans</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;t;i++) &#123;</span><br><span class="line">			<span class="type">int</span>[] num = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">26</span>];</span><br><span class="line">			<span class="type">int</span> <span class="variable">max</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">				num[ch[j][i]-<span class="string">&#x27;a&#x27;</span>]++;</span><br><span class="line">				<span class="keyword">if</span>(max&lt;num[ch[j][i]-<span class="string">&#x27;a&#x27;</span>]) &#123;</span><br><span class="line">					max = num[ch[j][i]-<span class="string">&#x27;a&#x27;</span>];</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			ans = ans + (n-max);</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println(ans);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第三章-排序"><a href="#第三章-排序" class="headerlink" title="第三章 排序"></a>第三章 排序</h1><h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p>思路：每一次循环将最大值 / 最小值放于向后移动。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] sort(<span class="type">int</span>[] a)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;a.length-<span class="number">1</span>;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">0</span>;j&lt;a.length-<span class="number">1</span>-i;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(a[j]&gt;a[j+<span class="number">1</span>])&#123;</span><br><span class="line">                <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> a[j+<span class="number">1</span>];</span><br><span class="line">                a[j+<span class="number">1</span>] = a[j];</span><br><span class="line">                a[j] = temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><p>思路：第 i 趟，把第 i 个元素放到前 i - 1 个有序的序列中 。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] InsertSort(<span class="type">int</span>[] a)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;a.length;i++)&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> a[i];<span class="comment">//处理第i个元素</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i-<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(;j&gt;=<span class="number">0</span> &amp;&amp; a[j]&gt;temp;j--)&#123;</span><br><span class="line">            a[j+<span class="number">1</span>] = a[j];<span class="comment">//大的元素往后移</span></span><br><span class="line">        &#125;</span><br><span class="line">        a[j+<span class="number">1</span>] = temp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p>思路：第 i 趟把从 i ~ 结尾最小的元素找到，放到 i 位置。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] SelectedSort(<span class="type">int</span>[] a)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;a.length;i++)&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">min</span> <span class="operator">=</span> i;<span class="comment">//存放i+1到最后最小的元素所在的下标</span></span><br><span class="line">     	<span class="keyword">for</span>(<span class="type">int</span> j=i+<span class="number">1</span>;j&lt;a.length;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(a[j]&lt;a[min])</span><br><span class="line">                min = j;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> a[i];</span><br><span class="line">        a[i] = a[min];</span><br><span class="line">        a[min] = temp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p>思路：将排序的区间分成若干个有跨度的子区间，对每一个子区间，进行插入排序，跨度不断 / 2 ，最终当跨度为 1 的时候，进行一个插入排序。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] shell(<span class="type">int</span>[] a)&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> <span class="variable">gap</span> <span class="operator">=</span> a.length/<span class="number">2</span>;gap&gt;<span class="number">0</span>;gap/=<span class="number">2</span>)&#123;</span><br><span class="line">        <span class="comment">//对每一分组进行直接插入排序</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=gap;i&lt;a.length;i++)&#123;</span><br><span class="line">            <span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i;</span><br><span class="line">            <span class="keyword">while</span>(j-gap&gt;=<span class="number">0</span> &amp;&amp; a[j-gap]&gt;a[j])&#123;<span class="comment">//大的往后移动</span></span><br><span class="line">                <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> a[j];</span><br><span class="line">                a[j] = a[j-gap];</span><br><span class="line">                a[j-gap] = temp;</span><br><span class="line">                j = j-gap;<span class="comment">//下一次继续从分组的前一个位置开始</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> a;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><p>思路：找出数组中的最大值和最小值，每个数都是在 min 和 max 之间，用一个长度为（max - min + 1）的数组 c 来存储每一个数出现的次数，然后将数组 c 转换为前缀和数组，则 c[ i ]，就表示不大于（i+min）的元素的个数，按照 c 数组还原排序结果。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">countSort</span><span class="params">(<span class="type">int</span>[] a)</span>&#123;</span><br><span class="line">	<span class="type">int</span>[] b = <span class="keyword">new</span> <span class="title class_">int</span>[a.length];</span><br><span class="line">    <span class="type">int</span> <span class="variable">max</span> <span class="operator">=</span> a[<span class="number">0</span>];min = a[<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;a.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(a[i]&gt;max) max = a[i];</span><br><span class="line">        <span class="keyword">if</span>(a[i]&lt;min) min = a[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">int</span> <span class="variable">dis</span> <span class="operator">=</span> max - min + ;</span><br><span class="line">    <span class="type">int</span>[] c = <span class="keyword">new</span> <span class="title class_">int</span>[dis];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;a.length;i++)</span><br><span class="line">        c[a[i]-min]++;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;c.length;i++)</span><br><span class="line">        c[i] = c[i] + c[i-<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=a.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        b[c[a[i]-min]-<span class="number">1</span>] = a[i];</span><br><span class="line">        c[a[i]-min]--;</span><br><span class="line">    &#125;</span><br><span class="line">    System.out.println(Arrays.toString(b));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第四章-数据结构基础"><a href="#第四章-数据结构基础" class="headerlink" title="第四章 数据结构基础"></a>第四章 数据结构基础</h1><h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h2><h4 id="为什么要用链表"><a href="#为什么要用链表" class="headerlink" title="为什么要用链表"></a>为什么要用链表</h4><p>数组作为一个顺序储存方式的数据结构，可是有大作为的，它的灵活使用为我们的程序设计带来了大量的便利；但是，数组最大的缺点就是我们的插入和删除时需要移动大量的元素，所以呢，大量的消耗时间，以及冗余度难以接收。</p><p>链表可以灵活地去解决这个问题，插入删除操作只需要修改指向的对象就可以了，不需要进行大量的数据移动操作。</p><h4 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h4><h6 id="初始化"><a href="#初始化" class="headerlink" title="初始化"></a>初始化</h6><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Node</span>&#123;<span class="comment">//定义结点类</span></span><br><span class="line">    <span class="type">int</span> value;<span class="comment">//本身的值</span></span><br><span class="line">    Node next;<span class="comment">//指向下一个结点</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(<span class="type">int</span> value, Node next)</span> &#123;</span><br><span class="line">        <span class="built_in">this</span>.value = value;</span><br><span class="line">        <span class="built_in">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">Node</span> <span class="variable">head</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(-<span class="number">1</span>,<span class="literal">null</span>);<span class="comment">//头结点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">end</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(-<span class="number">1</span>, <span class="literal">null</span>);<span class="comment">//尾结点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">per</span> <span class="operator">=</span> head;</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=<span class="number">10</span>;i++) &#123;</span><br><span class="line">    per.next = <span class="keyword">new</span> <span class="title class_">Node</span>(i, <span class="literal">null</span>);</span><br><span class="line">    per = per.next;</span><br><span class="line">&#125;</span><br><span class="line">per.next = end;</span><br></pre></td></tr></table></figure><h6 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h6><p>​ 插入前：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102205.png" alt="image-20231118203551162"></p><p>​ 插入后：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102206.png" alt="image-20231118203544620"></p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">Node now;<span class="comment">//待插入结点</span></span><br><span class="line">now.next = head.next;<span class="comment">//此节点的next为插入位置上一个结点的下一个结点</span></span><br><span class="line">head.next = now;<span class="comment">//此节点位置的上一个结点的下一个结点为now</span></span><br></pre></td></tr></table></figure><h6 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h6><p>​ 删除前：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102207.png" alt="image-20231118203608364"></p><p>​ 删除后：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102208.png" alt="image-20231118203627478"></p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Node now;<span class="comment">//待删除结点</span></span><br><span class="line">head.next = now.next;</span><br></pre></td></tr></table></figure><h4 id="双链表"><a href="#双链表" class="headerlink" title="双链表"></a>双链表</h4><h6 id="初始化-1"><a href="#初始化-1" class="headerlink" title="初始化"></a>初始化</h6><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">N</span>&#123;</span><br><span class="line">    N last;</span><br><span class="line">    <span class="type">int</span> value;</span><br><span class="line">    N next;</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">N</span><span class="params">(N last, <span class="type">int</span> value, N next)</span> &#123;</span><br><span class="line">        <span class="built_in">this</span>.last = last;</span><br><span class="line">        <span class="built_in">this</span>.value = value;</span><br><span class="line">        <span class="built_in">this</span>.next = next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">Node</span> <span class="variable">first</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(<span class="literal">null</span>,-<span class="number">1</span>,<span class="literal">null</span>);<span class="comment">//头结点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">end</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(<span class="literal">null</span>,-<span class="number">1</span>, <span class="literal">null</span>);<span class="comment">//尾节点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">per</span> <span class="operator">=</span> first;</span><br><span class="line"><span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=<span class="number">10</span>;i++) &#123;</span><br><span class="line">    per.next = <span class="keyword">new</span> <span class="title class_">N</span>(per,i, <span class="literal">null</span>);</span><br><span class="line">    per = per.next;</span><br><span class="line">&#125;</span><br><span class="line">end.last = per;</span><br><span class="line">per.next = end;</span><br></pre></td></tr></table></figure><h6 id="插入-1"><a href="#插入-1" class="headerlink" title="插入"></a>插入</h6><p>​ 插入前：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102209.png" alt="image-20231118203704325"></p><p>​ 插入后：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102210.png" alt="image-20231118203719212"></p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Node now;<span class="comment">//待插入结点</span></span><br><span class="line">now.next = first.next;</span><br><span class="line">first.next.last = now;</span><br><span class="line">first.next = now;</span><br><span class="line">now.last = first;</span><br></pre></td></tr></table></figure><h6 id="删除-1"><a href="#删除-1" class="headerlink" title="删除"></a>删除</h6><p>​ 删除前：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102211.png" alt="image-20231118203733885"></p><p>​ 删除后：</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102212.png" alt="image-20231118203744884"></p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">Node now;<span class="comment">//待删除结点</span></span><br><span class="line">now.last.next = now.next;</span><br><span class="line">now.next.last = now.last;</span><br></pre></td></tr></table></figure><h4 id="例题：左移右移（双链表解法）"><a href="#例题：左移右移（双链表解法）" class="headerlink" title="例题：左移右移（双链表解法）"></a>例题：左移右移（双链表解法）</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/2219/learning/">左移右移 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102213.png" alt="image-20231118203759075"></p><p>思路：</p><p>​ 1.创建双链表并完成初始化，初始元素为 1 ~ n；</p><p>​ 2.无论 x 左移或右移，都要先将 x 从原位置删除，为了便于获取 x 对应的 Node 结点，用 Map 存储 x 和 value 为 x 的结点；</p><p>​ 3.如果 x 为左移，就将 x 对应的 Node 结点插入到头结点后；</p><p>​ 4.如果 x 为右移，就将 x 对应的 Node 结点插入到尾节点前；</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"><span class="keyword">import</span> java.util.HashMap;</span><br><span class="line"><span class="keyword">import</span> java.util.Map;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 左移右移_双链表 &#123;</span><br><span class="line">	<span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">		Node up;</span><br><span class="line">		<span class="type">int</span> value;</span><br><span class="line">		Node down;</span><br><span class="line">		<span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(Node up, <span class="type">int</span> value, Node down)</span> &#123;</span><br><span class="line">			<span class="built_in">this</span>.up = up;</span><br><span class="line">			<span class="built_in">this</span>.value = value;</span><br><span class="line">			<span class="built_in">this</span>.down = down;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException&#123;</span><br><span class="line">        <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">        <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">        String[] s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">        <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> Integer.parseInt(s[<span class="number">0</span>]);</span><br><span class="line">        <span class="type">int</span> <span class="variable">m</span> <span class="operator">=</span> Integer.parseInt(s[<span class="number">1</span>]);</span><br><span class="line">        Map&lt;Integer, Node&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;&gt;();</span><br><span class="line">        <span class="type">Node</span> <span class="variable">first</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(<span class="literal">null</span>, -<span class="number">1</span>, <span class="literal">null</span>);</span><br><span class="line">        <span class="type">Node</span> <span class="variable">last</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(<span class="literal">null</span>, -<span class="number">1</span>, <span class="literal">null</span>);</span><br><span class="line">        <span class="type">Node</span> <span class="variable">no</span> <span class="operator">=</span> first;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++) &#123;</span><br><span class="line">        	no.down = <span class="keyword">new</span> <span class="title class_">Node</span>(no, i, <span class="literal">null</span>);</span><br><span class="line">        	no = no.down;</span><br><span class="line">        	map.put(i, no);</span><br><span class="line">        &#125;</span><br><span class="line">        last.up = no;</span><br><span class="line">        no.down = last;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        	s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">        	<span class="type">char</span> <span class="variable">ch</span> <span class="operator">=</span> s[<span class="number">0</span>].charAt(<span class="number">0</span>);</span><br><span class="line">        	<span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> Integer.parseInt(s[<span class="number">1</span>]);</span><br><span class="line">        	<span class="type">Node</span> <span class="variable">node</span> <span class="operator">=</span> map.get(x);</span><br><span class="line">        	node.up.down = node.down;</span><br><span class="line">        	node.down.up = node.up;</span><br><span class="line">        	<span class="keyword">if</span>(ch==<span class="string">&#x27;L&#x27;</span>) &#123;</span><br><span class="line">        		node.down = first.down;</span><br><span class="line">        		first.down.up = node;</span><br><span class="line">        		first.down = node;</span><br><span class="line">        		node.up = first;</span><br><span class="line">        	&#125;<span class="keyword">else</span> &#123;</span><br><span class="line">        		node.up = last.up;</span><br><span class="line">        		last.up.down = node;</span><br><span class="line">        		node.down = last;</span><br><span class="line">        		last.up = node;</span><br><span class="line">        	&#125;</span><br><span class="line">        &#125;</span><br><span class="line">        no = first.down;</span><br><span class="line">        <span class="keyword">while</span>(no!=last) &#123;</span><br><span class="line">        	System.out.print(no.value+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        	no = no.down; </span><br><span class="line">        &#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h4 id="栈-1"><a href="#栈-1" class="headerlink" title="栈"></a>栈</h4><p>栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。</p><p>栈顶（Top）：线性表允许进行插入删除的那一端。</p><p>栈底（Bottom）：固定的，不允许进行插入和删除的另一端。</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102214.png" alt="image-20231118203841538"></p><h4 id="常用方法"><a href="#常用方法" class="headerlink" title="常用方法"></a>常用方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">Stack&lt;Integer&gt; stack = <span class="keyword">new</span> <span class="title class_">Stack</span>();</span><br><span class="line"><span class="type">boolean</span> <span class="variable">is</span> <span class="operator">=</span> stack.isEmpty();<span class="comment">//判断此栈是否为空</span></span><br><span class="line"><span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> stack.peek();<span class="comment">//获取栈顶的元素，但不删除</span></span><br><span class="line"><span class="type">int</span> <span class="variable">m</span> <span class="operator">=</span> stacl.pop();<span class="comment">//获取并删除栈顶的元素</span></span><br><span class="line">stack.push(<span class="number">10</span>);<span class="comment">//将10压入栈中</span></span><br><span class="line">stack.clear();<span class="comment">//清空栈</span></span><br></pre></td></tr></table></figure><h4 id="判断括号序列是否合法"><a href="#判断括号序列是否合法" class="headerlink" title="判断括号序列是否合法"></a>判断括号序列是否合法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(String s)</span>&#123;</span><br><span class="line">    Stack&lt;Character&gt; stack = <span class="keyword">new</span> <span class="title class_">Stack</span>();</span><br><span class="line">    <span class="type">char</span>[] ch = s.toCharArray();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;ch.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(ch[i]==<span class="string">&#x27;(&#x27;</span>)</span><br><span class="line">            stack.push(ch[i]);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(stack.isEmpty())</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            stack.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h2><h4 id="队列-1"><a href="#队列-1" class="headerlink" title="队列"></a>队列</h4><p>队列（queue）是一种先进先出的、操作受限的线性表。</p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102215.png" alt="image-20231118203904215"></p><p>队列这种数据结构非常容易理解，就像我们平时去超市买东西，在收银台结账的时候需要排队，先去排队的就先结账出去，排在后面的就后结账，有其他人再要过来结账，必须排在队尾不能在队中间插队。</p><h4 id="常用方法-1"><a href="#常用方法-1" class="headerlink" title="常用方法"></a>常用方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Queue&lt;Integer&gt; queue = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line">queue.peek();<span class="comment">//获取队头元素，但不删除</span></span><br><span class="line">queue.poll();<span class="comment">//获取并删除队头元素</span></span><br><span class="line">queue.clear();<span class="comment">//清空队列</span></span><br><span class="line">queue.push(<span class="number">11</span>);<span class="comment">//将11存放到队列中</span></span><br></pre></td></tr></table></figure><h4 id="例题：左移右移（栈-队列解法）"><a href="#例题：左移右移（栈-队列解法）" class="headerlink" title="例题：左移右移（栈 + 队列解法）"></a>例题：左移右移（栈 + 队列解法）</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/2219/learning/">左移右移 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102217.png" alt="image-20231118203920958"></p><p>思路：</p><p>​ 1.如果一个数先移动到最左边，再移动到最右边，那么最后输出的时候这个数一定是在最右边，也就是一个数最终出现在哪里，以他最后一次出现为准；</p><p>​ 2.为了避免一个数重复判断，而且要以他最后一次出现时的 L 和 R 操作为最终操作，所以可以先将全部输入分别存放到 char 类型数组和 int 类型数组中，然后逆序判断，并且用一个数组来表示这个 x 有没有出现过；</p><p>​ 3.因为要对输入做逆序操作，所以，逆序时最后出现的 L 对应的 x 在输出的最前面，然后之后出现的 L 对应的 x 依次输出，即先入先出，可以用队列来存储进行 L 操作的 x ；</p><p>​ 4.逆序时最后出现的 R 对应的 x 在输出的最后面，然后之后出现的 R 对应的 x 依次在前，即后入先出，可以用栈来存储进行 R 操作的 x ；</p><p>​ 5.输出时，先输出队列中的元素，然后将 1 ~ n 中没有出现过的值按序输出，最后输出栈中的元素；</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"><span class="keyword">import</span> java.util.Stack;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 左移右移_栈_队列 &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException&#123;</span><br><span class="line">        <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">        <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">        String[] s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">        <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> Integer.parseInt(s[<span class="number">0</span>]);</span><br><span class="line">        <span class="type">int</span> <span class="variable">m</span> <span class="operator">=</span> Integer.parseInt(s[<span class="number">1</span>]);</span><br><span class="line">        <span class="type">int</span>[] a = <span class="keyword">new</span> <span class="title class_">int</span>[n+<span class="number">1</span>];</span><br><span class="line">        <span class="type">char</span>[] c = <span class="keyword">new</span> <span class="title class_">char</span>[m];</span><br><span class="line">        <span class="type">int</span>[] x = <span class="keyword">new</span> <span class="title class_">int</span>[m];</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        	s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">            c[i] = s[<span class="number">0</span>].charAt(<span class="number">0</span>);</span><br><span class="line">            x[i] = Integer.parseInt(s[<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">        Stack&lt;Integer&gt; r = <span class="keyword">new</span> <span class="title class_">Stack</span>&lt;&gt;();</span><br><span class="line">        Queue&lt;Integer&gt; l = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=m-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--) &#123;</span><br><span class="line">        	<span class="keyword">if</span>(a[x[i]]==<span class="number">0</span>) &#123;<span class="comment">//判断x[i]是否出现过</span></span><br><span class="line">        		a[x[i]] = <span class="number">1</span>;<span class="comment">//若x[i]没有出现过</span></span><br><span class="line">        		<span class="keyword">if</span>(c[i]==<span class="string">&#x27;L&#x27;</span>)</span><br><span class="line">        			l.add(x[i]);</span><br><span class="line">        		<span class="keyword">else</span></span><br><span class="line">        			r.push(x[i]);</span><br><span class="line">        	&#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(l.size()!=<span class="number">0</span>) <span class="comment">//输出队列中元素</span></span><br><span class="line">        	System.out.print(l.poll()+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++) </span><br><span class="line">        	<span class="keyword">if</span>(a[i]==<span class="number">0</span>) <span class="comment">//a[i]为0，表示i没有出现过</span></span><br><span class="line">        		System.out.print(i+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        <span class="keyword">while</span>(r.size()!=<span class="number">0</span>) <span class="comment">//输出栈中元素</span></span><br><span class="line">        	System.out.print(r.pop()+<span class="string">&quot; &quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第五章-分治算法"><a href="#第五章-分治算法" class="headerlink" title="第五章 分治算法"></a>第五章 分治算法</h1><h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><p>思路：先把数组从中间分成前后两部分，然后分别对前后两部分进行排序，再将排好序的两部分数据合并在一起</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">mergeSort</span><span class="params">(<span class="type">int</span>[] a,<span class="type">int</span> left,<span class="type">int</span> right)</span>&#123;<span class="comment">//待排序数组，要排序的范围[left,right]</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (left+right)&gt;&gt;<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(left&lt;right)&#123;</span><br><span class="line">        mergeSort(a,left,mid);</span><br><span class="line">        mergeSort(a,mid+<span class="number">1</span>,right);</span><br><span class="line">        merge(a,left,mid,right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">merge</span><span class="params">(<span class="type">int</span>[] a,<span class="type">int</span> left,<span class="type">int</span> mid,<span class="type">int</span> right)</span>&#123;</span><br><span class="line">    <span class="type">int</span>[] temp = <span class="keyword">new</span> <span class="title class_">int</span>[right-left+<span class="number">1</span>];<span class="comment">//临时数组，用来归并</span></span><br><span class="line">    <span class="type">int</span> i=left,j=mid+<span class="number">1</span>,k=<span class="number">0</span>;<span class="comment">//左半段用i指向，右半段用j指向，temp数组用k指向</span></span><br><span class="line">    <span class="keyword">while</span>(i&lt;=mid &amp;&amp; j&lt;=right)&#123;</span><br><span class="line">        <span class="keyword">if</span>(a[i]&lt;a[j])</span><br><span class="line">            temp[k++] = a[i++];</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            temp[k++] = a[j++];   </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=mid) temp[k++] = a[i++];</span><br><span class="line">    <span class="keyword">while</span>(j&lt;=right) temp[k++] = a[j++];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> x=<span class="number">0</span>;x&lt;temp.length;x++)&#123;</span><br><span class="line">        a[left+x] = temp[x];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><p>思路：</p><p>(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。</p><p>(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。</p><p>(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。</p><p>(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">quickSort</span><span class="params">(<span class="type">int</span>[] a,<span class="type">int</span> left,<span class="type">int</span> right)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left&gt;right) <span class="keyword">return</span>;<span class="comment">//区间擦肩而过，无效，不需要进行递归</span></span><br><span class="line">    <span class="type">int</span> i=left,j=right,temp = a[left];<span class="comment">//a[left]作为基准点</span></span><br><span class="line">    <span class="keyword">while</span>(i!=j)&#123;</span><br><span class="line">        <span class="keyword">while</span>(a[j]&gt;=a[temp] &amp;&amp; j&gt;i)</span><br><span class="line">            j--;<span class="comment">//只要a[j]大于基准点继续往前移动j</span></span><br><span class="line">        <span class="keyword">if</span>(j&gt;i)</span><br><span class="line">            a[i++] = a[j];</span><br><span class="line">        <span class="keyword">while</span>(a[i]&lt;=a[temp] &amp;&amp; i&lt;j)</span><br><span class="line">            i++;</span><br><span class="line">        <span class="keyword">if</span>(i&lt;j)</span><br><span class="line">            a[j--] = a[i];</span><br><span class="line">    &#125;</span><br><span class="line">    a[i] = temp;<span class="comment">//基准点元素放到最终位置</span></span><br><span class="line">    quickSort(a,left,i-<span class="number">1</span>);</span><br><span class="line">    quickSort(a,i+<span class="number">1</span>,right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="快速幂"><a href="#快速幂" class="headerlink" title="快速幂"></a>快速幂</h2><p>思路：每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。</p><p>例：3^10^ = 3*3*3*3*3*3*3*3*3*3 ，尽量想办法把指数变小来，这里的指数为10。</p><p>3^10^=(3*3)(3*3)(3*3)(3*3)(3*3)</p><p>3^10^=(3*3)^5^</p><p>3^10^=9^5^</p><p>此时指数由10缩减一半变成了5，而底数变成了原来的平方，求3^10^原本需要执行10次循环操作，求9^5^却只需要执行5次循环操作，但是3^10^却等于9^5^,用一次（底数做平方操作）的操作减少了原本一半的循环量，特别是在幂特别大的时候效果非常好，例如2^10000^=4^5000^,底数只是做了一个小小的平方操作，而指数就从10000变成了5000，减少了5000次的循环操作。</p><p>现在问题是如何把指数5变成原来的一半，5是一个奇数，5的一半是2.5，但是指数不能为小数，因此不能简单粗暴地直接执行5/2，然而，这里还有另一种方法能表示9^5^，9^5^=9^4^*9^1^</p><p>此时抽出了一个底数的一次方，这里即为9^1^，这个9^1^先单独移出来,剩下的9^4^又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作。9^5^=81^2^*9^1^</p><p>把指数缩小一半，底数执行平方操作，9^5^=6561^1^*9^1^</p><p>此时，发现指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，应该抽出了一个底数的一次方，这里即为6561^1^，这个6561^1^先单独移出来，但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。</p><p>9^5^=（6561^0^)(9^1^)(6561^1^)=1(9^1^)(6561^1^)=(9^1^)(6561^1^)=9*6561=59049</p><p>能够发现，最后的结果是9*6561。所以能发现一个规律：最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。</p><p>继续优化：</p><p>b%2==1可以用更快的“位运算”来代替，例如：b&amp;1。因为如果b为偶数，则其二进制表示的最后一位一定是0；如果b是奇数，则其二进制表示的最后一位一定是1。将他们分别与1的二进制做“与”运算，得到的就是b二进制最后一位的数字了，是0则为偶数，是1则为奇数。例如9是奇数，则9&amp;1=1；而8是偶数，则8&amp;1=0；因此奇偶数的判断就可以用“位运算”来替换了。</p><p>m = m / 2也可以用更快的移位操作来代替，例如：6的四位二进制为0110，而6/2=3,3的四位二进制为0011，可以发现，a的一半，结果为a的二进制码向右移一位，即m &gt;&gt;=1。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">long</span> <span class="title function_">num</span><span class="params">(<span class="type">long</span> n, <span class="type">long</span> m, <span class="type">long</span> p)</span> &#123;</span><br><span class="line">    <span class="type">long</span> <span class="variable">result</span> <span class="operator">=</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (m &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> ((m &amp; <span class="number">1</span> ) == <span class="number">1</span>) &#123;</span><br><span class="line">            result = result * n % p;</span><br><span class="line">        &#125;</span><br><span class="line">        m &gt;&gt;= <span class="number">1</span>;</span><br><span class="line">        n = (n * n) % p;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第六章-搜索"><a href="#第六章-搜索" class="headerlink" title="第六章 搜索"></a>第六章 搜索</h1><h2 id="全排列"><a href="#全排列" class="headerlink" title="全排列"></a>全排列</h2><h4 id="DFS解法"><a href="#DFS解法" class="headerlink" title="DFS解法"></a>DFS解法</h4><p>思路：将此过程看做一棵树，每一个结点下都会有 n 个结点表示下一个数，首先先将全部 n^n^ 个结果全部得出，然后剪枝，减去有重复数字出现的情况。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> depth,String ans,<span class="type">int</span> n)</span>&#123;<span class="comment">//当前深搜的层数，目前的结果，目标层数</span></span><br><span class="line">    <span class="keyword">if</span>(depth==n)&#123;<span class="comment">//当前深搜层数=目标层数</span></span><br><span class="line">        System.out.println(ans);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    	<span class="keyword">if</span>(!ans.contains(i+<span class="string">&quot;&quot;</span>))<span class="comment">//只有当还没有用过i的时候，才会在现在的基础上继续往下拓展</span></span><br><span class="line">			dfs(depth+<span class="number">1</span>,ans+i;n);<span class="comment">//进入下一层，ans记录为进入下一层的值，n不变</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="BFS解法"><a href="#BFS解法" class="headerlink" title="BFS解法"></a>BFS解法</h4><p>思路：先将有重复数字的结果得出，每一个数后都可以跟 n 中可能，那么将这 n 中可能存入队列中，然后重复此过程，直到字符串的长度为 n 时，得到结果；剪枝，如果这个数字已经用过了，就直接只用下一个数字。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">bfs</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    Queue&lt;String&gt; queue = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        queue.offer(i+<span class="string">&quot;&quot;</span>);</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="type">String</span> <span class="variable">now</span> <span class="operator">=</span> queue.poll();</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;<span class="comment">//每个结点都向下产生n个结果</span></span><br><span class="line">            <span class="keyword">if</span>(now.contains(i+<span class="string">&quot;&quot;</span>))<span class="comment">//i已经使用过了</span></span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="type">String</span> <span class="variable">son</span> <span class="operator">=</span> head + i;</span><br><span class="line">            <span class="keyword">if</span>(son.length()==n)</span><br><span class="line">                System.out.println(son);</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                queue.offer(son);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="整数划分"><a href="#整数划分" class="headerlink" title="整数划分"></a>整数划分</h2><p>思路：对 n 进行划分后， n 可以被不超过 n 个数累加得到，进行累加的每一个数，也可以被不超过它本身个数累加得到。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> n,<span class="type">int</span> nowget,<span class="type">int</span> max,String ans)</span>&#123;<span class="comment">//要划分的数，现在已经得到的值，目前划分已经用到的最大值，具体拆分方法</span></span><br><span class="line">    <span class="keyword">if</span>(nowget==n)&#123;</span><br><span class="line">        ans = ans.substring(<span class="number">0</span>,ans.length()-<span class="number">1</span>);</span><br><span class="line">        System.out.println(n+<span class="string">&quot;=&quot;</span>+ans);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=n-nowget;i++)&#123;<span class="comment">//从nowget累加到n</span></span><br><span class="line">        <span class="keyword">if</span>(i&gt;=max)<span class="comment">//只有当下一个数不小于我之前用过的最大值时，才能保证整个结果为非递减</span></span><br><span class="line">            dfs(n,nowget+i,i,ans+i+<span class="string">&quot;+&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h2><h4 id="例题：路径之谜"><a href="#例题：路径之谜" class="headerlink" title="例题：路径之谜"></a>例题：路径之谜</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/89/learning/">路径之谜 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102218.png" alt="image-20231118204002349"></p><p>思路：</p><p>​ 1.从入口点开始，到达每一个点都将对应位置北墙和西墙的箭靶数减一，每一个点，都可以继续向四个方向继续前进（前提是这个点没有走过，在城堡范围内，且这个点对应的两个箭靶的数字不为 0 ）。</p><p>​ 2.如果已经到了终点，就要判断现在每一个箭靶上的数字是否都已经变为 0 ，如果是，那么此时走的路径就是正确解，否则就需要回溯，考虑其他的行走路线。</p><p>​ 3.回溯：因为要从已经走过的点退回来，所以在已经走过的点上射的箭要收回，箭靶数加一，并且标记此点为还没有走过。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 路径之谜 &#123;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span>[] path;<span class="comment">//记录最终路径，因为底面为n*n，所以走出需要2*n步</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> n;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span>[] cntx;<span class="comment">//存储北墙箭靶数字</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span>[] cnty;<span class="comment">//存储西墙箭靶数字</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">boolean</span>[][] visited;<span class="comment">//判断此点有没有走过</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> dx[] = &#123;<span class="number">1</span>, <span class="number">0</span>, -<span class="number">1</span>, <span class="number">0</span>&#125;;<span class="comment">//到下一个点x坐标的变化量</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> dy[] = &#123;<span class="number">0</span>, <span class="number">1</span>, <span class="number">0</span>, -<span class="number">1</span>&#125;;<span class="comment">//到下一个点y坐标的变化量</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">	<span class="keyword">static</span> <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException &#123;</span><br><span class="line">    	n = Integer.parseInt(in.readLine());</span><br><span class="line">    	cntx = <span class="keyword">new</span> <span class="title class_">int</span>[n];</span><br><span class="line">    	cnty = <span class="keyword">new</span> <span class="title class_">int</span>[n];</span><br><span class="line">    	path = <span class="keyword">new</span> <span class="title class_">int</span>[n * n];</span><br><span class="line">    	visited = <span class="keyword">new</span> <span class="title class_">boolean</span>[n][n];</span><br><span class="line">    	String[] s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">    	<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">    		cntx[i] = Integer.parseInt(s[i]);</span><br><span class="line">    	&#125;</span><br><span class="line">    	s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">    	<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">    		cnty[i] = Integer.parseInt(s[i]);</span><br><span class="line">    	&#125;</span><br><span class="line">    	dfs(<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>);<span class="comment">//从0,0位置开始走,目前走了0步</span></span><br><span class="line">  &#125;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">dfs</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y, <span class="type">int</span> step)</span> &#123;</span><br><span class="line">		path[step] = y * n + x; <span class="comment">//将该点编号记录到路径中</span></span><br><span class="line">		visited[x][y] = <span class="literal">true</span>;<span class="comment">//将该点标记为已经走过的状态</span></span><br><span class="line">		cntx[x]--;<span class="comment">//拔掉对应北墙的箭</span></span><br><span class="line">		cnty[y]--;<span class="comment">//拔掉对应西墙的箭</span></span><br><span class="line">		<span class="keyword">if</span> (x == n - <span class="number">1</span> &amp;&amp; y == n - <span class="number">1</span> &amp;&amp; check())&#123;<span class="comment">//判断是否到达终点</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt;= step; i++)&#123;<span class="comment">//输出答案</span></span><br><span class="line">				System.out.print(path[i]+<span class="string">&quot; &quot;</span>);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">4</span>; i++)&#123;<span class="comment">//上下左右四个方向搜索下一步</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">xx</span> <span class="operator">=</span> x + dx[i], yy = y + dy[i];</span><br><span class="line">             <span class="comment">//下一步(xx,yy)未走过且在地图范围内</span></span><br><span class="line">			<span class="keyword">if</span> (<span class="number">0</span> &lt;= xx &amp;&amp; xx &lt;= n-<span class="number">1</span> &amp;&amp; yy &gt;= <span class="number">0</span> &amp;&amp; yy &lt;= n-<span class="number">1</span>&amp;&amp; !visited[xx][yy] )&#123;</span><br><span class="line">				<span class="keyword">if</span> (cntx[xx] &gt; <span class="number">0</span> &amp;&amp; cnty[yy] &gt; <span class="number">0</span>)&#123;<span class="comment">//该点对应箭靶上有箭，说明该点可以走</span></span><br><span class="line">					dfs(xx, yy, step + <span class="number">1</span>);<span class="comment">//搜索下一步</span></span><br><span class="line">                    <span class="comment">//要从xx,yy点回来,在xx,yy点射的箭要复原，并重新标记xx,yy点没有走过</span></span><br><span class="line">					visited[xx][yy] = <span class="literal">false</span>;</span><br><span class="line">					cntx[xx]++;</span><br><span class="line">					cnty[yy]++;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">()</span> &#123;<span class="comment">//判断到达终点时,是否箭靶数都已经归零</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (cntx[i] != <span class="number">0</span> || cnty[i] != <span class="number">0</span>)</span><br><span class="line">				<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="例题：迷宫"><a href="#例题：迷宫" class="headerlink" title="例题：迷宫"></a>例题：迷宫</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/602/learning/">迷宫 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102219.png" alt="image-20231118204041308"></p><p>思路：从起点开始，将从此点能到达的点存储到队列中，每次获取并删除队列中的第一个元素，并将其能到达且还未到达过的点（若此点已经到达过，则表示当前处理的这条路径不是最短路径）存储到队列中，若已经到达终点，则此路径为最短路径。如果队列中已经没有元素，但仍未到达迷宫终点，则表示此迷宫无解</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> class 迷宫 &#123;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> num;<span class="comment">//存储迷宫最短路径所需要的步数</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> <span class="variable">xsize</span> <span class="operator">=</span> <span class="number">30</span>;<span class="comment">//迷宫大小30行50列</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span> <span class="variable">ysize</span> <span class="operator">=</span> <span class="number">50</span>;</span><br><span class="line">	<span class="keyword">static</span> <span class="type">char</span>[][] arr = <span class="keyword">new</span> <span class="title class_">char</span>[xsize][ysize];<span class="comment">//存储迷宫：0表示路，1表示墙</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">boolean</span>[][] help = <span class="keyword">new</span> <span class="title class_">boolean</span>[xsize][ysize];<span class="comment">//判断此点是否已经做过</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">int</span>[][] dir = &#123;&#123;<span class="number">1</span>,<span class="number">0</span>&#125;,&#123;<span class="number">0</span>,-<span class="number">1</span>&#125;,&#123;<span class="number">0</span>,<span class="number">1</span>&#125;,&#123;-<span class="number">1</span>,<span class="number">0</span>&#125;&#125;;<span class="comment">//四个方向横纵坐标的变化量</span></span><br><span class="line">	<span class="keyword">static</span> <span class="type">char</span>[] sign = &#123;<span class="string">&#x27;D&#x27;</span>,<span class="string">&#x27;L&#x27;</span>,<span class="string">&#x27;R&#x27;</span>,<span class="string">&#x27;U&#x27;</span>&#125;;<span class="comment">//表示四个方向</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException &#123;</span><br><span class="line">		<span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">		<span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;xsize;i++)&#123;</span><br><span class="line">			arr[i] = in.readLine().toCharArray();</span><br><span class="line">		&#125;</span><br><span class="line">		out.println(bfs());</span><br><span class="line">		out.print(num);<span class="comment">//额外输出最短路径需要多少步</span></span><br><span class="line">		out.flush();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">static</span> String <span class="title function_">bfs</span><span class="params">()</span> &#123;</span><br><span class="line">		Queue&lt;Node&gt; list = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();<span class="comment">//队列</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">y</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">runnum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		list.add(<span class="keyword">new</span> <span class="title class_">Node</span>(x,y,<span class="string">&quot;&quot;</span>,runnum));<span class="comment">//将起点存储到队列中</span></span><br><span class="line">		<span class="keyword">while</span>(!list.isEmpty())&#123;<span class="comment">//判断队列是否为空，若为空，则此迷宫没有通路</span></span><br><span class="line">			<span class="type">Node</span> <span class="variable">now</span> <span class="operator">=</span> list.poll();<span class="comment">//获取队列中的第一个元素并删除</span></span><br><span class="line">			help[now.x][now.y] = <span class="literal">true</span>;<span class="comment">//将此点标记为已经走过</span></span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;i++)&#123;<span class="comment">//循环四次，对四个方向进行处理</span></span><br><span class="line">				<span class="type">int</span> <span class="variable">xx</span> <span class="operator">=</span> now.x + dir[i][<span class="number">0</span>];<span class="comment">//移动后的x坐标</span></span><br><span class="line">				<span class="type">int</span> <span class="variable">yy</span> <span class="operator">=</span> now.y + dir[i][<span class="number">1</span>];<span class="comment">//移动后的y坐标</span></span><br><span class="line">                  <span class="comment">//此点在迷宫范围内，未走过，不是墙</span></span><br><span class="line">				<span class="keyword">if</span>(check(xx,yy) &amp;&amp; help[xx][yy]==<span class="literal">false</span> &amp;&amp; arr[xx][yy]==<span class="string">&#x27;0&#x27;</span>)&#123;</span><br><span class="line">					list.add(<span class="keyword">new</span> <span class="title class_">Node</span>(xx,yy,now.num + sign[i],now.runnum + <span class="number">1</span>));<span class="comment">//将此点存入队列中</span></span><br><span class="line">					<span class="keyword">if</span>(xx==xsize-<span class="number">1</span> &amp;&amp; yy==ysize-<span class="number">1</span>)&#123;<span class="comment">//如果已经到了迷宫终点</span></span><br><span class="line">						num = now.runnum + <span class="number">1</span>;<span class="comment">//所需步数+1（now.runnum是到达迷宫终点前一步所需要的步数）</span></span><br><span class="line">						<span class="keyword">return</span> now.num + sign[i];<span class="comment">//返回通过迷宫的方式</span></span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="string">&quot;&quot;</span>;<span class="comment">//空字符串，表示此迷宫无通路</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">static</span> <span class="type">boolean</span> <span class="title function_">check</span><span class="params">(<span class="type">int</span> xx, <span class="type">int</span> yy)</span> &#123;<span class="comment">//判断此点是否在迷宫范围内</span></span><br><span class="line">		<span class="keyword">return</span> xx&gt;=<span class="number">0</span> &amp;&amp; yy&gt;=<span class="number">0</span> &amp;&amp; xx&lt;xsize &amp;&amp; yy&lt;ysize;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Node</span>&#123;</span><br><span class="line">		<span class="type">int</span> x;<span class="comment">//x坐标</span></span><br><span class="line">		<span class="type">int</span> y;<span class="comment">//y坐标</span></span><br><span class="line">		<span class="type">int</span> runnum;<span class="comment">//到达此点最短步数</span></span><br><span class="line">		String num;<span class="comment">//到达此点的方式</span></span><br><span class="line">		<span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y,String num ,<span class="type">int</span> runnum)</span> &#123;</span><br><span class="line">			<span class="built_in">super</span>();</span><br><span class="line">			<span class="built_in">this</span>.x = x;</span><br><span class="line">			<span class="built_in">this</span>.y = y;</span><br><span class="line">			<span class="built_in">this</span>.num = num;</span><br><span class="line">			<span class="built_in">this</span>.runnum = runnum;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第七章-贪心"><a href="#第七章-贪心" class="headerlink" title="第七章 贪心"></a>第七章 贪心</h1><h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><p>所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。<br>贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。</p><h2 id="例题-1"><a href="#例题-1" class="headerlink" title="例题"></a>例题</h2><h4 id="例题：合并果子"><a href="#例题：合并果子" class="headerlink" title="例题：合并果子"></a>例题：合并果子</h4><p>题目链接：<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/741/learning/">合并果子 - 蓝桥云课 (lanqiao.cn)</a></p><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102220.png" alt="image-20231118204125650"></p><p>思路：</p><p>​ 1.要保证最终耗费的体力最小，那么就可以每次合并都把目前数量最少的两堆果子合并，耗费的体力就是这两堆果子树木的和，然后合并后又可以作为新的一堆果子继续去判断，直到最终只剩一堆。</p><p>​ 2.可以借助PriorityQueue优先队列，队列中第一个元素就是最小值，即可每次获取队列中前两个元素，然后将他们的和再次添加至队列中，直到最终队列中只剩一个元素。</p><p>​ 3.以题目样例为例：对于数组{pi}={1, 2, 9}，Huffman树的构造过程如下：</p><p>​ 3.1找到{1, 2, 9}中最小的两个数，分别是 1 和 2 ，</p><p>​ 3.2从{pi}中删除它们并将和 3 加入，得到{3, 9}，体力消耗为 3 。</p><p>​ 3.3找到{3， 9}中最小的两个数，分别是 3 和 9 ，</p><p>​ 3.4从{pi}中删除它们并将和 12 加入，得到{12}，费用为 12 。</p><p>​ 3.5现在，数组中只剩下一个数12，构造过程结束，总费用为3 + 12 = 15。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.io.BufferedReader;</span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InputStreamReader;</span><br><span class="line"><span class="keyword">import</span> java.io.OutputStreamWriter;</span><br><span class="line"><span class="keyword">import</span> java.io.PrintWriter;</span><br><span class="line"><span class="keyword">import</span> java.util.PriorityQueue;</span><br><span class="line"><span class="keyword">import</span> java.util.Scanner;</span><br><span class="line"><span class="keyword">import</span> java.util.Spliterator;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Main</span> &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException&#123;</span><br><span class="line">        <span class="type">BufferedReader</span> <span class="variable">in</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">BufferedReader</span>(<span class="keyword">new</span> <span class="title class_">InputStreamReader</span>(System.in));</span><br><span class="line">        <span class="type">PrintWriter</span> <span class="variable">out</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">PrintWriter</span>(<span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(System.out));</span><br><span class="line">        <span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> Integer.parseInt(in.readLine());</span><br><span class="line">        <span class="type">long</span> <span class="variable">sum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        PriorityQueue&lt;Long&gt; queue = <span class="keyword">new</span> <span class="title class_">PriorityQueue</span>&lt;&gt;();</span><br><span class="line">        String[] s = in.readLine().split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">0</span>;i&lt;s.length;i++) &#123;</span><br><span class="line">            queue.add(Long.parseLong(s[i]));</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">long</span> <span class="variable">number</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(queue.size()!=<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="type">long</span> <span class="variable">a</span> <span class="operator">=</span> queue.poll();<span class="comment">//获取最小的一堆</span></span><br><span class="line">            <span class="type">long</span> <span class="variable">b</span> <span class="operator">=</span> queue.poll();<span class="comment">//获取最小的一堆</span></span><br><span class="line">            number = number + ( a + b );<span class="comment">//合并这两堆耗费的体力</span></span><br><span class="line">            queue.add((a+b));<span class="comment">//将合并后的结果放回优先队列中</span></span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println(number);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第八章-树"><a href="#第八章-树" class="headerlink" title="第八章 树"></a>第八章 树</h1><h2 id="树的相关概念"><a href="#树的相关概念" class="headerlink" title="树的相关概念"></a>树的相关概念</h2><h4 id="什么是树"><a href="#什么是树" class="headerlink" title="什么是树"></a>什么是树</h4><p>树(Tree)是 n ( n ≧ 0 )个结点的有限集。n=0时称为空树。在任意一颗非空树中：有且仅有一个特定的称为根的结点。当n&gt;1时，其余结点可分为 m ( m &gt; 0 ) 个互不相交的有限集T1、T2、T3……、Tm，其中每个集合本身又是一棵树，并且称为根的子树。</p><h4 id="树的基本概念"><a href="#树的基本概念" class="headerlink" title="树的基本概念"></a>树的基本概念</h4><p><img src="https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202311182102221.png" alt="image-20231118204210164"></p><h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><h4 id="什么是二叉树"><a href="#什么是二叉树" class="headerlink" title="什么是二叉树"></a>什么是二叉树</h4><p>二叉树是n(n&gt;=0)个结点的有限集合，该集合或者为空集（空二叉树）、或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。</p><h4 id="二叉树的特点"><a href="#二叉树的特点" class="headerlink" title="二叉树的特点"></a>二叉树的特点</h4><p>​ 1.二叉树中每个结点最多有两颗子树，度没有超过2的。</p><p>​ 2.左子树和右子树是有顺序的，不能颠倒。</p><h4 id="满二叉树"><a href="#满二叉树" class="headerlink" title="满二叉树"></a>满二叉树</h4><p>在二叉树中，所有的分支节点都有左子树和右子树，并且所有的叶子都在同一层。</p><h4 id="完全二叉树"><a href="#完全二叉树" class="headerlink" title="完全二叉树"></a>完全二叉树</h4><p>​ 1.叶子结点只能出现在最下面两层。</p><p>​ 2.最下层的叶子一定集中在左部连续位置。</p><p>​ 3.倒数第二层，若有叶子结点，一定在右部连续位置。</p><p>​ 4.如果结点度为1，则该结点只有左孩子。</p><p>​ 5.同样结点的二叉树，完全二叉树的深度最小。</p><h2 id="二叉树的创建和嵌套打印"><a href="#二叉树的创建和嵌套打印" class="headerlink" title="二叉树的创建和嵌套打印"></a>二叉树的创建和嵌套打印</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//结点类</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">TreeNode</span>&#123;</span><br><span class="line">    <span class="type">int</span> data;<span class="comment">//结点存放的数据</span></span><br><span class="line">    TreeNode left;<span class="comment">//左孩子</span></span><br><span class="line">    TreeNode right;<span class="comment">//右孩子</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">TreeNode</span><span class="params">(<span class="type">int</span> data,TreeNode left,TreeNOde right)</span>&#123;</span><br><span class="line">        <span class="built_in">this</span>.data = data;</span><br><span class="line">        <span class="built_in">this</span>.left = left;</span><br><span class="line">        <span class="built_in">this</span>.right = right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Scanner;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Tree</span>&#123;</span><br><span class="line">    TreeNode root;<span class="comment">//整棵树的根节点</span></span><br><span class="line">    <span class="type">Scanner</span> <span class="variable">sc</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Scanner</span>(System.in);</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">Tree</span><span class="params">()</span>&#123;</span><br><span class="line">        root = <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> TreeNode <span class="title function_">createBinaryTree</span><span class="params">()</span>&#123;<span class="comment">//树的创建</span></span><br><span class="line">        TreeNode t;<span class="comment">//当前树的根节点</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> sc.nextInt();</span><br><span class="line">        <span class="keyword">if</span>(x==<span class="number">0</span>) t=<span class="literal">null</span>;</span><br><span class="line">        <span class="keyword">else</span>&#123;</span><br><span class="line">            t = <span class="keyword">new</span> <span class="title class_">TreeNode</span>();</span><br><span class="line">            t.data = x;</span><br><span class="line">            t.left = createBinaryTree();</span><br><span class="line">            t.right = createBinaryTree();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> t;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">printTree</span><span class="params">(TreeNode t)</span>&#123;<span class="comment">//树的打印</span></span><br><span class="line">        <span class="keyword">if</span>(t!=<span class="literal">null</span>)&#123;</span><br><span class="line">            System.out.print(t.data);</span><br><span class="line">            <span class="keyword">if</span>(t.left!=<span class="literal">null</span> || t.right!=<span class="literal">null</span>)&#123;</span><br><span class="line">                System.out.print(<span class="string">&quot;(&quot;</span>);</span><br><span class="line">                printTree(t.left);</span><br><span class="line">                <span class="keyword">if</span>(t.right!=<span class="literal">null</span>) System.out.print(<span class="string">&quot;,&quot;</span>);</span><br><span class="line">                printTree(t.left);</span><br><span class="line">                System.out.print(<span class="string">&quot;)&quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="前中后序层次遍历"><a href="#前中后序层次遍历" class="headerlink" title="前中后序层次遍历"></a>前中后序层次遍历</h2><h4 id="前序遍历"><a href="#前序遍历" class="headerlink" title="前序遍历"></a>前序遍历</h4><p>思路：对于每个结点，优先处理结点本身，再处理它的左孩子，最后处理它的右孩子。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">preOrder</span><span class="params">(TreeNode root)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root!=<span class="literal">null</span>)&#123;</span><br><span class="line">        System.out.print(root.data+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        preOrder(root.left);</span><br><span class="line">        preOrder(root.right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="中序遍历"><a href="#中序遍历" class="headerlink" title="中序遍历"></a>中序遍历</h4><p>思路：对于每个结点，优先处理它的左孩子，再处理它本身，最后处理它的右孩子。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">midOrder</span><span class="params">(TreeNode root)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root!=<span class="literal">null</span>)&#123;</span><br><span class="line">        midOrder(root.left);</span><br><span class="line">        System.out.print(root.data+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        midOrder(root.right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="后序遍历"><a href="#后序遍历" class="headerlink" title="后序遍历"></a>后序遍历</h4><p>思路：对于每个结点，优先处理它的左节点，再处理它的右节点，最后处理它本身。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">postOrder</span><span class="params">(TreeNode root)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root!=<span class="literal">null</span>)&#123;</span><br><span class="line">        postOrder(root.left);</span><br><span class="line">       	postOrder(root.right);</span><br><span class="line">        System.out.print(root.data+<span class="string">&quot; &quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="层次遍历"><a href="#层次遍历" class="headerlink" title="层次遍历"></a>层次遍历</h4><p>思路：广度优先搜索；处理根节点的每一个子结点，再处理子结点的每一个子结点……直至结束。</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">levelOrder</span><span class="params">(TreeNode t)</span>&#123;</span><br><span class="line">    Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;();</span><br><span class="line">    <span class="keyword">if</span>(t==<span class="literal">null</span>) <span class="keyword">return</span>;</span><br><span class="line">    queue.offer(t);</span><br><span class="line">    <span class="keyword">while</span>(!queue.isEmpty())&#123;</span><br><span class="line">        <span class="type">TreeNode</span> <span class="variable">head</span> <span class="operator">=</span> queue.poll();</span><br><span class="line">        System.out.print(head.data);</span><br><span class="line">        <span class="keyword">if</span>(head.left!=<span class="literal">null</span>)</span><br><span class="line">        	queue.offer(head.left);</span><br><span class="line">        <span class="keyword">if</span>(head.right!=<span class="literal">null</span>)</span><br><span class="line">        	queue.offer(head.right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="求二叉树深度"><a href="#求二叉树深度" class="headerlink" title="求二叉树深度"></a>求二叉树深度</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">int</span> <span class="title function_">treeDepth</span><span class="params">(TreeNode root)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root==<span class="literal">null</span>) <span class="keyword">return</span> <span class="number">0</span>;<span class="comment">//此结点不存在</span></span><br><span class="line">    <span class="keyword">return</span> Math.max(treeDepth(root.left),treeDepth(root.right))+<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="求二叉树叶子结点个数"><a href="#求二叉树叶子结点个数" class="headerlink" title="求二叉树叶子结点个数"></a>求二叉树叶子结点个数</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">int</span> <span class="title function_">TreeLeaf</span><span class="params">(TreeNode root)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root==<span class="literal">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(root.left==<span class="literal">null</span> &amp;&amp; root.right==<span class="literal">null</span>) <span class="keyword">return</span> <span class="number">1</span>;<span class="comment">//此结点没有孩子，表示此结点为叶子结点</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> treeLeaf(root.left) + treeLeaf(root.right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="重建二叉树"><a href="#重建二叉树" class="headerlink" title="重建二叉树"></a>重建二叉树</h2><p>思路：</p><p>​ 1.前序遍历为：根，{左子树}，{右子树}；可得，前序遍历的第一个结点为根结点；</p><p>​ 2.中序遍历为：{左子树}，根，{右子树}；可得，结点的左侧为它的左孩子树，右侧为它的右孩子树；</p><p>​ 3.重复此过程，重建此二叉树；</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title function_">f</span><span class="params">(String pre,String mid)</span>&#123;<span class="comment">//前序遍历结果，中序遍历结果</span></span><br><span class="line">    <span class="keyword">if</span>(pre.length()==<span class="number">0</span>) <span class="keyword">return</span> <span class="string">&quot;&quot;</span>;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(pre.length==<span class="number">1</span>) <span class="keyword">return</span> pre;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">pos</span> <span class="operator">=</span> mid.indexOf(pre.charAt(<span class="number">0</span>));</span><br><span class="line">        <span class="type">String</span> <span class="variable">left</span> <span class="operator">=</span> f(pre.substring(<span class="number">1</span>,pos+<span class="number">1</span>),mid.substring(<span class="number">0</span>,pos));</span><br><span class="line">        <span class="type">String</span> <span class="variable">right</span> <span class="operator">=</span> f(pre.substring(pos+<span class="number">1</span>),mid.substring(pos+<span class="number">1</span>));</span><br><span class="line">        <span class="keyword">return</span> left+right+pre.charAt(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="第九章-图"><a href="#第九章-图" class="headerlink" title="第九章 图"></a>第九章 图</h1><h1 id="第十章-动态规划"><a href="#第十章-动态规划" class="headerlink" title="第十章 动态规划"></a>第十章 动态规划</h1><h4 id="LCS-最长公共子序列"><a href="#LCS-最长公共子序列" class="headerlink" title="LCS 最长公共子序列"></a>LCS 最长公共子序列</h4><p>思路：</p><p>​ 1.用一个数组 dp[ i ][ j ] 表示 S 字符串中前 i 个字符与 T 字符串中前 j 个字符的最长上升子序列，那么 dp[ i+1 ][ j+1 ] 就是S 字符串中前 i+1 个字符与 T 字符串中前 j+1 个字符的最长上升子序列；</p><p>​ 2.如果此时 S 中的第 i+1 个字符与 T 中的第 j+1 个字符相同，那么 dp[ i+1 ][ j+1 ] = dp[ i ][ j ] + 1;</p><p>​ 3.如果此时 S 中的第 i+1 个字符与 T 中的第 j+1 个字符不同，那么 dp[ i+1 ][ j+1 ] = Math.max ( dp[ i+1 ][ j ] , dp[ i ][ j+1 ] );</p><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">LCS</span><span class="params">(String s,String t)</span>&#123;</span><br><span class="line">    <span class="type">int</span>[][] dp=<span class="keyword">new</span> <span class="title class_">int</span>[s.length()+<span class="number">1</span>][t.length()+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>;i&lt;=s.length();i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j=<span class="number">1</span>;j&lt;=t.length();j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(s.charAt(i-<span class="number">1</span>)==t.charAt(j-<span class="number">1</span>))</span><br><span class="line">                dp[i][j]=dp[i-<span class="number">1</span>][j-<span class="number">1</span>]+<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                dp[i][j]=Math.max(dp[i][j-<span class="number">1</span>],dp[i-<span class="number">1</span>][j]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> dp[len1][len2];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></article><div class="mt-12 pt-6 border-t border-gray-200"><span class="bg-gray-100 dark:bg-gray-700 px-2 py-1 m-1 text-sm rounded-md transition-colors hover:bg-gray-200"><a href="/tags/%E5%85%AB%E8%82%A1%E6%96%87/">八股文</a> </span><span class="bg-gray-100 dark:bg-gray-700 px-2 py-1 m-1 text-sm rounded-md transition-colors hover:bg-gray-200"><a href="/tags/%E9%9D%A2%E8%AF%95%E9%80%86%E8%A2%AD/">面试逆袭</a></span></div><div class="flex justify-between mt-12 pt-6 border-t border-gray-200"><div><a href="/posts/eb30969e.html" class="text-sm text-gray-400 hover:text-gray-500 flex justify-center"><iconify-icon width="20" icon="ri:arrow-left-s-line" data-inline="false"></iconify-icon>002-JZoffer</a></div><div><a href="/posts/d4ab7a61.html" class="text-sm text-gray-400 hover:text-gray-500 flex justify-center">校园失物招领系统<iconify-icon width="20" icon="ri:arrow-right-s-line" data-inline="false"></iconify-icon></a></div></div><div class="article-comments mt-12"><div class="giscus-container mt-8 pt-8 border-t border-gray-200 dark:border-gray-700"><script src="https://giscus.app/client.js" data-repo="WL2O2O/CS_GUIDER_Giscus" data-repo-id="R_kgDOJYdTQw" data-category="Announcements" data-category-id="DIC_kwDOJYdTQ84CWKC6" data-mapping="pathname" data-strict="0" data-reactions-enabled="1" data-emit-metadata="0" data-input-position="top" data-theme="preferred_color_scheme" data-lang="en" crossorigin="anonymous" async></script></div><script>function updateGiscusTheme(){const e=document.querySelector("iframe.giscus-frame");if(e){const s=document.documentElement.classList.contains("dark");e.contentWindow.postMessage({giscus:{setConfig:{theme:s?"dark":"light"}}},"https://giscus.app")}}window.addEventListener("message",e=>{"https://giscus.app"===e.origin&&e.data.giscus&&e.data.giscus.resizeHeight&&updateGiscusTheme()});const observer=new MutationObserver(()=>{updateGiscusTheme()});observer.observe(document.documentElement,{attributes:!0,attributeFilter:["class"]})</script></div></section><script src="/lib/clipboard.min.js"></script><script async src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-MML-AM_CHTML"></script><script type="text/x-mathjax-config">MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
  });</script><script type="text/x-mathjax-config">MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });</script><script src="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script><script>$(document).ready(()=>{mermaid.initialize({theme:"default",logLevel:3,flowchart:{curve:"linear"},gantt:{axisFormat:"%m/%d/%Y"},sequence:{actorMargin:50}})})</script><script src="/lib/fancybox/fancybox.umd.min.js"></script><script>$(document).ready(()=>{$(".post-content").each((function(a){$(this).find("img").each((function(){if(!$(this).parent().hasClass("fancybox")&&!$(this).parent().is("a")){var a=this.alt;a&&$(this).after('<span class="fancybox-alt">'+a+"</span>"),$(this).wrap('<a class="fancybox-img" href="'+this.src+'" data-fancybox="gallery" data-caption="'+a+'"></a>')}})),$(this).find(".fancybox").each((function(){$(this).attr("rel","article"+a)}))})),Fancybox.bind('[data-fancybox="gallery"]',{})})</script><script src="/lib/tocbot/tocbot.min.js"></script><script>$(document).ready(()=>{tocbot.init({tocSelector:".post-toc",contentSelector:".post-content",headingSelector:"h1, h2, h3",hasInnerContainers:!0})})</script></main><footer class="flex flex-col h-40 items-center justify-center text-gray-400 text-sm"><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div class="flex items-center gap-2"><span>Visitors</span> <span id="busuanzi_value_site_uv"></span> <span>Page Views</span> <span id="busuanzi_value_site_pv"></span></div><div class="flex items-center gap-2"><a target="_blank" href="https://creativecommons.org/licenses/by-nc-sa/4.0/" style="color:inherit">CC BY-NC-SA 4.0</a> <span>© 2025</span><iconify-icon width="18" icon="emojione-monotone:desktop-computer"></iconify-icon><a href="https://github.com/wl2o2o" target="_blank" rel="noopener noreferrer">CS_GUIDER</a></div><div class="flex items-center gap-2"><span>Powered by</span> <a href="https://hexo.io/" target="_blank" rel="noopener noreferrer">Hexo</a> <span>&</span> <a href="https://github.com/wl2o2o" target="_blank" rel="noopener noreferrer">CS_GUIDER</a></div></footer><div class="back-to-top box-border fixed right-6 z-1024 -bottom-20 rounded py-1 px-1 bg-slate-900 opacity-60 text-white cursor-pointer text-center dark:bg-slate-600"><span class="flex justify-center items-center text-sm"><iconify-icon width="18" icon="ion:arrow-up-c" id="go-top"></iconify-icon><span id="scrollpercent"><span>0</span> %</span></span></div><script src="/js/main.js"></script><script src="/js/search.js"></script><script>$(document).ready((function(){const t=document.getElementById("maple");Array.from({length:"10"}).map(()=>{const e=document.createElement("div"),a=.5*Math.random()+.5,l=2*Math.random()-1,n=Math.random()*t.clientWidth,i=-Math.random()*t.clientHeight;return e.className="maple",e.style.width=24*a+"px",e.style.height=24*a+"px",e.style.left=n+"px",e.style.top=i+"px",e.style.setProperty("--maple-fall-offset",l),e.style.setProperty("--maple-fall-height",Math.abs(i)+t.clientHeight+"px"),e.style.animation=`fall ${10/"0.3"}s linear infinite`,e.style.animationDelay=-10/"0.3"+"s",t.appendChild(e),e})}))</script><div class="fixed top-0 bottom-0 left-0 right-0 pointer-events-none print:hidden" id="maple"></div></body></html>